This chapter describes the complete interface of TGraph, the base object for all non-linear containers in the Containers Library object hierarchy. All non-linear containers are ultimately derived from TGraph, so the topics discussed in this chapter apply to all non-linear containers in the library.
In this chapter you will learn how to:
- Use keys to identify items in a container
- Retrieve data from a container using keys
- Make comparisons of keys case-sensitive or case-insensitive
- Allow duplicates in containers
- Restrict the scope of some methods using ExactMatch
- Move through items in a non-linear container
- Use iterative methods for finding items and conditionally
moving through a non-linear container
- Determine the number of items that satisfy certain search
criteria
Using keys
A key is something that identifies a particular data item in a data set. Keys can be of any type. For example, a key could be the last name of a client, a person's social security number or perhaps a combination of both.
Graphs (or non-linear containers) are key-based containers. This means that all items in a graph must have a key, and that the keys of all items in the same graph must be of the same type. Graphs use these keys to sort the items in the container, and then provide indexed access to your data. In other words, they allow you to retrieve an item simply by providing the key of the item that you are looking for.
As an example, let's assume that you want to provide indexed access to a set of TClient records that have the following structure:
PClient = ^TClient;
TClient = record
ClientNo : LongInt;
LastName : string[40];
FirstName : string[20];
MiddleI : Char;
end;
We will use ClientNo as the key of our data items.
To use a graph to store a set of TClient records, the first thing you must do is teach the graph how to retrieve the key of a data item in the container. This is done by overriding the KeyOf method in TGraph. In our case, KeyOf must return a pointer to the ClientNo field of TClient:
TMyGraph = object(TB+Tree)
function KeyOf(Item: Pointer): Pointer; virtual;
end;
TMyGraph.KeyOf(Item: Pointer): Pointer;
begin
KeyOf := @(PClient(Item)^.ClientNo);
end;
By default, TGraph assumes that keys of items in the container are of type string (or PString if working in a Windows application). However, if you are using keys of another type (as in our example) you must also teach the graph how to compare the keys of two different data items. This is done by overriding the Compare method:
TMyGraph = object(TB+Tree)
function Compare(Key1, Key2 : Pointer): Integer; virtual;
end;
function TMyGraph.Compare(Key1, Key2 : Pointer): Integer;
begin
if LongInt(Key1)^ < LongInt(Key2)^
then Compare := -1
else if LongInt(Key1)^ = LongInt(Key2)^
then Compare := 0
else Compare := 1;
end;
Compare must return a result as follows:
-1 if Key1 < Key2
0 if Key1 = Key2
1 if Key1 > Key2
Once the container knows how to extract the key of an item and how to compare the keys of two different items, you are ready to start adding data to the graph. In the following sections you will learn how to find and retrieve data from a graph, using the keys of items in the graph.
Retrieving data from a graph
Retrieving data from a graph is as easy as indicating the key of the item that you want to retrieve. TGraph provides two methods for retrieving data: KeyFirst and KeyLast.
KeyFirst and KeyLast
KeyFirst returns the first occurrence of an item with a key that matches the key you specify. For example,
function FindFirstExact (Key: Pointer): Pointer;
begin
MyGraph^.ExactMatch := True;
FindFirstExact := MyGraph^.KeyFirst(Key);
end;
The ExactMatch field indicates TGraph to return an item only if the item has exactly the same key as the one specified. ExactMatch is explained in more detail later in this section.
KeyLast returns the last occurrence of an item with a key that matches the key you specify. For example:
function FindLastExact(Key : Pointer): Pointer;
begin
MyGraph^.ExactMatch := True;
FindLastExact := MyGraph^.KeyLast(Key);
end;
If no duplicates are allowed in the container, KeyLast is equivalent to KeyFirst. Additional information on allowing duplicates in a graph can be found later in this chapter.
ExactMatch
ExactMatch is a boolean field that allows you to restrict the scope of some methods to only items with a particular key. When ExactMatch is True, searches will only return an item if the item matches exactly the key that you specified. If ExactMatch is False, searches will either return an item with a key that matches exactly the key you specified or, if not found, the next higher or lower item found. For example, the following code will either return the first item with a key of 'Mark', or return an item with the next higher key (e.g., 'Markus').
function FindFirstNearest;
var
Key : string;
begin
MyGraph^.ExactMatch := False;
Key := 'Mark';
FindFirstNearest := MyGraph^.KeyFirst(@Key);
end;
If we used KeyLast instaed, it would return the first item with a key lower than the key you specified if an exact match is not found:
function FindLastNearest;
var
Key : string;
begin
MyGraph^.ExactMatch := False;
Key := 'Markus';
FindLastNearest := MyGraph^.KeyLast(@Key);
end;
All methods in TGraph that take a key as a parameter are relative to ExactMatch. Throughout the rest of this chapter, more information on how ExactMatch affects the behavior of each method is provided after the function of the respective method has been explained.
Note: Since ExactMatch can be constantly changing, we recommend that you always set the value of ExactMatch to the appropriate value before calling a TGraph method. This is not necessary, however, if you never change the value of ExactMatch. ExactMatch is by default True.
The CaseSensitive field
When a TGraph descendant searches for an item with a given key, it compares the key of each item with the key it is looking for. By default, all comparisons are sensitive to the case of the keys; that is, all comparisons of keys in TGraph descendants are case-sensitive. In some situations, however, you may want TGraph to ignore the case of keys when looking for an item. You can control this by changing the value of the CaseSensitive field.
CaseSensitive tells TGraph whether key comparisons are case-sensitive or not. If CaseSensitive is True, uppercase letters are considered to be different and smaller to their lowercase equivalents. Otherwise, uppercase letters are considered to be equal to their lowercase equivalents. For example:
CaseSensitive = True, 'A' < 'a'
CaseSensitive = False, 'A' = 'a'
When changing the value of CaseSensitive, remember to change it immediately after creating the container. Otherwise, items inserted in the container before CaseSensitive was changed, will not be sorted correctly.
Allowing duplicate keys
Sometimes you will need to store different items in a container that have the same key. These two items have duplicate keys and are said to be duplicate items, despite the fact that they cannot be identical in all aspects. By default, TGraph descendants do not allow the insertion of duplicate items. If you try to insert an item with a key that matches the key of an item already in the graph, the container will abort the operation and report a "duplicate key" error.
You can insert duplicate items by changing the value of the Duplicates field in TGraph. Duplicates determines whether the container accepts items with duplicate keys. When Duplicates is False, the container will only accept the first item inserted with a given key. When Duplicates is True, the container will insert duplicate items immediately before the first existing item with the same key. This way, you will always find first the newest item first when performing a search in the container.
Warning! After setting Duplicates to True, you should never set it back to False unless you are certain there are no duplicate items in the container. Otherwise, the container will not be able to correctly structure the data or in most cases even access correctly the data already inserted.
Updating and replacing data
TGraph allows you to update and replace data by means of the ItemUpdate and ItemReplace methods. These methods take two parameters: a pointer to the old item that must be replaced and a pointer to the new item that will be inserted in its place. When called, they will search for the old item in the container and if found, proceed to replace or update it with the new item.
ItemPut replaces an item, but does not disposes of the item being replaced. It is equivalent to:
Delete(OldItem);
Insert(NewItem);
After the new item is inserted, you must manually free the item by calling the container's FreeItem method. ItemReplace, on the other hand, will both delete and dispose of the item being replaced.
NewItem := NewItem;
Key := 'Keaton';
OldItem := MyGraph^.KeyFirst(@Key);
NewItem^.Key := OldItem^.Key;
{... add new information to NewItem ...}
MyGraph^.ItemReplace(OldItem, NewItem);
Be aware that in graphs you can't change the key of an item in the container simply by changing the value of the key field in the item. To keep the integrity of the key order in a graph, you must either delete the item, change the item's key and then reinsert it, or create a new item, fill the fields of the new item with the appropriate data and the new key and then use ItemPut to insert the item.
Important! ItemReplace will insert the new item in exactly the same position in the graph where the old item is stored. Therefore, you must only use this method if both items have the same key, or if you are absolutely sure that the key order in the container will not be corrupted by the new insertion. If the key of both items is different, you should use ItemPut instead.
Moving in a graph
TGraph implements a series of methods that will allow you to move through the items a in graph, one item at a time. These methods are First, Next, Last and Prev. These methods differ from their TSequence equivalents in the type of seed values they use. In TGraph, methods use data items as their seed values. TSequence methods, on the other hand, use the index number of items as their seed values.
First
First returns the first item in key order stored in a graph. Note that this is not necessarily the first item that you inserted.
Item := MyGraph^.First;
The item returned by First can be used as a seed value in other methods like Next or Prev. Usually you will use First together with Next or Prev to move through the items in a container.
Next
Next takes one parameter, Item, and returns a pointer to the item following Item in key order.
with MyGraph^ do
begin
ExactMatch := False;
if Status > ctOk
then Status := ctOk;
Item := First;
while Status = ctOk do
begin
{...do something with item...}
Item := Next(Item);
end;
end;
The item returned by Next can be used as a seed value in other methods (e.g. Prev) or in another call to Next.
This method is relative to ExactMatch. If ExactMatch is True, Next will only return the next item if it has the same key as Item. Otherwise, if ExactMatch is False, Next will always return the next item regardless of its key. In the previous example, we needed to set ExactMatch to False to be able to visit all items in the graph. In the next example, however, we will set ExactMatch to True so that we visit only those items that have a particular key (in this case, 'Allen'):
with MyGraph^ do
begin
ExactMatch := False;
Key := 'Allen';
if Status > ctOk
then Status := ctOk;
Item := KeyFirst(@Key);
while Status = ctOk do
begin
{...do something with item...}
Item := Next(Item);
end;
end;
Since ExactMatch is used by other methods to behave in different ways, in most situations it is necessary to set ExactMatch to the appropriate value before calling this method.
Last
Last returns the last item in key order stored in a graph. Note that this is not necessarily the last item you inserted.
Item := MyGraph^.Last;
The item returned by Last can be used as a seed value in other methods like Prev or Next. Usually you will use Last together with Prev or Next to move through the items in a container.
Prev
Prev takes one parameter, Item, and returns a pointer to the item preceding Item in key order.
with MyGraph^ do
begin
ExactMatch := False;
if Status > ctOk
then Status := ctOk;
Item := Last;
while Status = ctOk do
begin
{...do something with item...}
Item := Prev(Item);
end;
end;
The item returned by Prev can be used as a seed value in other methods (e.g. Next) or in another call to Prev.
This method is relative to ExactMatch. If ExactMatch is True, Prev will only return the preceding item if it has the same key as Item. Otherwise, if ExactMatch is False, Prev will always return the preceding item regardless of its key. For example, in the following code we set ExactMatch to True so that we visit only those items that have a particular key (in this case, 'West'):
with MyGraph^ do
begin
ExactMatch := False;
Key := 'West';
if Status > ctOk
then Status := ctOk;
Item := KeyLast(@Key);
while Status = ctOk do
begin
{...do something with item...}
Item := Prev(Item);
end;
end;
Since ExactMatch is used by other methods to behave in different ways, in most situations it is necessary to set ExactMatch to the appropriate value before calling this method.
Iterative methods
Additional iterative methods in TGraph allow you to quickly find any item in a graph or conditionally move through all the items stored in it. These iterative methods work just like First, KeyFirst, Next, Prev, Last and KeyLast, but allow you to filter the items that are actually visited in a search.
The FirstThat and LastThat iterators
FirstThat and LastThat iterators provide an easy way of finding items in a container. FirstThat returns the first item in a container that satisfies a search criterion while LastThat returns the last item in a container that satisfies a search criterion.
These iterators take a pointer to a far local boolean function of type TTestFunction and return an item accordingly. This item can then be used as a seed value (or starting point) in other methods like NextThat or PrevThat.
procedure FindWinners;
function IsWinner(Item : PMyObject): Boolean; far;
begin
IsWinner := Item^.LotteryNumber := '2736491';
end;
begin
with MyGraph^ do
begin
if Status > ctOk
then Status := ctOk;
Item := FirstThat(@IsWinner);
while Status = ctOk do
begin
DisplayWinner(Item);
Item := NextThat(@IsWinner, Item);
end;
end;
end;
Remember to be careful about what sort of functions you call with iterators. Remember that the functions cannot be an object's methods and that it must be local to (nested in the same block with) the routine that is calling it. Functions must also be declared as far functions, either with the far directive or with the $F+ compiler directive. Finally, the functions must take a pointer to a container item as their only parameter.
KeyFirstThat and KeyLastThat
The KeyFirstThat and KeyLastThat iterators are FirstThat and LastThat equivalents that let you find items in a graph that have an specific key and also satisfy a search criterion. These methods are relative to ExactMatch. If ExactMatch is True, they will return not return an item unless it matches exactly the key provided. Otherwise, if ExactMatch is False, KeyFirstThat will return the next higher item that satisfies Test and KeyLastThat will return the next lower item that satisfies Test.
Since ExactMatch is used by other methods to behave in different ways, in most situations it is necessary to set ExactMatch to the appropriate value before calling this method.
The NextThat and PrevThat methods
When used together with FirstThat and LastThat, the NextThat and PrevThat iterators provide a way of conditionally moving through a container. That is, the let you select or filter the items that you want to visit when moving in a container.
These iterators take two parameters: a pointer to a far local boolean function of type TTestFunction and the item where you want to start the search in the container. The item returned can then be used as a seed value (or starting point) in other calls to NextThat and PrevThat.
procedure DisplayReversePrimes;
function IsPrime(Item : PMyObject) : Boolean; far;
begin
IsPrime := NumberIsPrime(Item^.Value);
end;
begin
with MyGraph^ do
begin
if Status > ctOk
then Status := ctOk;
Item := LastThat(@IsPrime, Index);
while Status = ctOk do
begin
Display(Item);
Item := PrevThat(@IsPrime, Item);
end;
end;
end;
NextThat and PrevThat are relative to ExactMatch. This means that if ExactMatch is True, they won't return an item unless it has exactly the same key as the key of the item passed as a seed value. Otherwise, if ExactMatch is False, they will return the item following or preceding the item passed as a seed value, regardless of the key of the seed item. For example, the following code will visit only those items with key 'Johnson' and that also match the condition given by Test:
with MyGraph^ do
begin
ExactMatch := True;
Key := 'Johnson';
if Status > ctOk
then Status := ctOk;
Item := KeyFirstThat(@Test, @Key);
while Status = ctOk do
begin
Display(Item);
Item := NextThat(@Test, Item);
end;
end;
The first call to either NextThat or PrevThat should always be preceded by a call to First, FirstThat, KeyFirstThat, Last, LastThat or KeyLastThat.. The function of these methods is to set the starting point of new searches, though this is not necessary if you already have a pointer to the item where you want to begin your search.
Find and FindThat
You can easily count the number of items with a certain key in a container or the number of those items that also match a search criteria, by using the Find and FindThat iterators.
Find takes a parameter to the key you want to look for, and returns in the Hits parameter the number of occurrences found. For example:
Key := 'Smith';
MyGraph^.Find(@Key, Hits);
FindThat searches in the container for all items with a key that matches the key you provide and that also a satisfy condition, given by the Test parameter which must be a pointer to a far local boolean function of type TTestFunction.
function CountChildren(LastName: string): LongInt;
var
Hits : LongInt;
function IsChildren(Item: PMyObject): Boolean; far;
begin
IsChildren := Item^.Age < 10;
end;
begin
MyGraph^.FindThat(@LastName, @IsChildren, Hits);
CountChildren := Hits;
end;
The value of ExactMatch has no effect on the result of the Find or FindThat methods.
